Fuzzing or fuzz-testing is a well-known technique for automatically identifying software bugs by providing a computer program with unexpected input and then monitoring the program execution for any anomalous behavior such as crashes, memory leaks or failing assertions.
In some cases, fuzz-testing is performed by running the program on a native processor which is capable of directly running the program's code. While the use of a native processor can yield a fast execution time, this option might not always be available due to limited access to such a testing environment or the fact that the program is written in a language for which there is not a compatible native processor, on which to run the program. Alternatively, such fuzz-testing can be performed, for example, by running the software in an emulated environment. One such well known emulator is Quick Emulator (QEMU) (https://www.qemu.org/).
Fuzz-testing can be performed on the entire program or any part thereof. When performed on a portion of a program, fuzz-testing is used to try to identify software bugs in a part of the program, such as an executable, a function, a library, a set of executables, a set of functions or a set of libraries. One such environment in which Fuzz-testing of a portion of a program could be performed is Unicorn (https://www.unicorn-engine.org/docs/beyond_qemu.html).
Another conventional method to perform fuzz-testing of a portion of a program involves executing the program under a debugger, followed by taking a snapshot of the state of the execution environment of the program, as it enters the part of the program in which fuzz-testing is sought. The snapshot of the state of the execution environment is, for example:                The state of the processors running the program;        The state of the memory used by the program;        The state of the file systems used by the program; and,        The state of the hardware devices used by the program.        
This taking of the snapshot of the state of the execution environment of the program, for example, is done using a debugger such as The GNU debugger (also known as gdb) or WinDBG. The snapshot is typically used at a later time in order to continue the execution of the program with different inputs. The different inputs could be generated by well-known fuzz-testing tools. One such well known tool for generating different inputs is “American Fuzzy Lop” (also known as AFL) (https://en.wikipedia.org/wiki/American_fuzzy_lop_(fuzzer)).
When performing fuzz-testing, it is sometimes advantageous to hook and divert certain functions. These hooked or diverted functions can be used to instrument (trace and monitor) the execution of the program under test, as well as to allow to execute the program under environments that are different than the environments in which the program normally executes. For example, a program might call a function that would normally perform a network service but which is not available under the testing environment. As another example, by hooking memory management function calls, the testing environment can monitor the memory usage of the program under test. Each of the hooks can, for example, after tracing the call, continue executing the original function, or alternatively, provide its own implementation.
A well-known concept in code analysis and testing is to test a basic block of code. Such a basic block typically includes a set of instructions, which have a single entry point and a single exit point such that the execution of instructions in the block normally starts with the entry point and completes with the exit point and where all other instructions are executed in a specific fixed order. The code of a program (or a part of a program) can normally be divided into distinct basic blocks.
Code coverage is a measure often used to describe the degree to which the code of a program, or a part thereof, is executed during a set of one or more executions. One possible metric for code coverage can be based on the number of unique, non-overlapping, basic blocks of a program, or a part thereof, which were executed during a set of such one or more executions.
When performing fuzz-testing, in many cases, it is advantageous to try and achieve a high level of code coverage. A high level of code coverage is typically correlated with higher chances of identifying unexpected behavior along with the inputs associated with it.
Coverage guided fuzzing is a process aimed at achieving high code coverage. For example, this is done by executing the program or a part thereof with different inputs and identifying any inputs that cause the execution of basic blocks, which were not executed previously.
As an example, assume a program consisting of N non-overlapping basic blocks, marked as A1, A2, . . . , An (where “n” represents the last element in a series of elements), and that takes as input a string of characters. Assume that under a first set of inputs, only basic blocks A1, A2, and A3 are executed. A fuzz-testing program might try a new string of characters such as ‘XXAA’ as input, and identify that this input causes basic block A4 to be executed. Such a fuzz-testing program can then try to feed the program with additional inputs, all of which start with the characters ‘XXAA’ in the hope that one or more of these will trigger the execution of additional basic blocks. One of these inputs, for example, ‘XXAAYY’ might cause the program to execute basic block A5. This process can be repeated recursively to achieve high levels of code coverage and ideally identify unexpected program behavior and the inputs associated with it. Other exemplary methods for modifying the input in order to achieve high code coverage could include mutating the input set by reordering the content of the input, flipping bits, duplicating a subset of the input, converting uppercase letters to lowercase or vice versa, and the like.
Another common technique used to identify the execution of new basic blocks relies on instrumenting the program, or portions thereof, and running it on a native processor. This instrumentation usually involves hooking each relevant basic block. The hooking is normally achieved by replacing the first instruction or instructions of each basic block of the program, or part thereof, with code that: 1) suspends execution of the basic block; 2) notifies the fuzz-testing environment that the basic block is being executed; and, 3) then resumes execution of the basic block. However, in some cases, such a technique cannot be used for various reasons including the fact that the instructions, which need to be placed at the beginning of the basic block, have alignment requirements, which cannot be satisfied, or that the code of any inserted hook will not end on an instruction boundary. Another example is the presence of PC (program counter) relative instructions whose semantics are likely to change if their position is altered by the addition of hooks in the various locations.
An alternative to this type of instrumentation is to emulate the execution of the basic block. In this approach, the emulator identifies the start of the execution of the basic block by, for example, monitoring the address of the instruction that needs to be executed, and identifying any matches with the beginning of a basic block. Such an approach is disadvantageous, as using an emulator is normally much slower than running natively.